/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.AddressableHeapFactory
import org.jheaps.MergeableAddressableHeap

/**
 * Reflected double ended heaps based on Fibonacci heaps. The heap is sorted
 * according to the [natural ordering][Comparable] of its keys, or by
 * a [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * This class implements a general technique which uses two
 * [FibonacciHeap]s to implement a double ended heap, described in detail
 * in the following
 * [paper](http://dx.doi.org/10.1016/S0020-0190(02)00501-X):
 *
 *  * C. Makris, A. Tsakalidis, and K. Tsichlas. Reflected min-max heaps.
 * Information Processing Letters, 86(4), 209--214, 2003.
 *
 *
 *
 *
 * This implementation provides amortized O(1) time for `insert`,
 * `findMin`, and `findMax`. Operations `decreaseKey`,
 * `increaseKey`, `deleteMin`, `deleteMax`, and `delete`
 * are amortized O(log(n)). The operation `meld` is amortized O(1).
 *
 *
 *
 * All the above bounds, however, assume that the user does not perform
 * cascading melds on heaps such as:
 *
 * <pre>
 * d.meld(e);
 * c.meld(d);
 * b.meld(c);
 * a.meld(b);
</pre> *
 *
 * The above scenario, although efficiently supported by using union-find with
 * path compression, invalidates the claimed bounds.
 *
 *
 *
 * Note that the ordering maintained by a this heap, like any heap, and whether
 * or not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the
 * `AddressableHeap` interface. (See `Comparable` or
 * `Comparator` for a precise definition of *consistent with
 * equals*.) This is so because the `AddressableHeap` interface is
 * defined in terms of the `equals` operation, but this heap performs all
 * key comparisons using its `compareTo` (or `compare`) method, so
 * two keys that are deemed equal by this method are, from the standpoint of
 * this heap, equal. The behavior of a heap *is* well-defined even if its
 * ordering is inconsistent with `equals`; it just fails to obey the
 * general contract of the `AddressableHeap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
class ReflectedFibonacciHeap<K, V>
/**
 * Constructs a new, empty heap, ordered according to the given comparator.
 * All keys inserted into the heap must be *mutually comparable* by
 * the given comparator: `comparator.compare(k1,
 * k2)` must not throw a `ClassCastException` for any keys `k1`
 * and `k2` in the heap. If the user attempts to put a key into the
 * heap that violates this constraint, the `insert(Object key)` call
 * will throw a `ClassCastException`.
 *
 * @param comparator
 * the comparator that will be used to order this heap. If
 * `null`, the [natural ordering][Comparable] of
 * the keys will be used.
 */
/**
 * Constructs a new, empty heap, using the natural ordering of its keys. All
 * keys inserted into the heap must implement the [Comparable]
 * interface. Furthermore, all such keys must be *mutually
 * comparable*: `k1.compareTo(k2)` must not throw a
 * `ClassCastException` for any keys `k1` and `k2` in the
 * heap. If the user attempts to put a key into the heap that violates this
 * constraint (for example, the user attempts to put a string key into a
 * heap whose keys are integers), the `insert(Object key)` call will
 * throw a `ClassCastException`.
 */
@JvmOverloads constructor(comparator: Comparator<in K?>? = null) : ReflectedHeap<K, V>(heapFactory = Factory<K,V>(), comparator=comparator) {
    // underlying heap factory
    private class Factory<K, V> : AddressableHeapFactory<K, HandleMap<K,V>, MergeableAddressableHeap<K, HandleMap<K,V>>> {
        override fun get(comparator: Comparator<in K?>?): MergeableAddressableHeap<K, HandleMap<K, V>> {
            return FibonacciHeap(comparator)
        }
    }

}
